P7324 [WC2021] 表达式求值

闲话

WC2021 我只得了 20 分，三道题总共 20 分。我是下场了突然后知后觉这件事的，主要原因是我开了 C++11，然后 T1 T2 都没分了。在洛谷上测本来能拿银牌的。T1 的乱搞能拿 48，还挺高的。

幸亏咱们陕西省选不看冬令营成绩。幸亏是在省选前犯的这个错误。告诫后人和自己，写题前一定要看编译选项，否则只能后悔莫及。

T2 场上写的是不带问号的 \(O(n|E|)\) 和带问号 \(O(n|E|m^2)\) 的 70 分暴力。后者可以用 minmax 卷积优化掉一个 \(m\) 获得 85 分的好成绩。

思路

首先要会上面提到的带问号的暴力，不需要优化。

我在场上写的是这样子的：

int a[maxn][10],but[maxn][10],tmp[10];
int* solve(int l,const int &r,const int *a){
    l++;
    int *ans=s[l]=='('?solve(l,to[l],a):but[l];//这里的 to 是预处理的括号匹配位置，完全可以用把 l 设成全局变量的方法解决
    l=s[l]=='('?to[l]+1:l+1;
    while(l+1<r){
        char op=s[l++];
        int *res=s[l]=='('?solve(l,to[l],a):but[l];
        l=s[l]=='('?to[l]+1:l+1;
        switch(op){
            case '<':{
                memset(tmp,0,sizeof tmp);
                for(int i=0;i<m;i++) for(int j=0;j<m;j++) if(a[i]<a[j]) tmp[i]=(tmp[i]+1ll*ans[i]*res[j])%mod;
                else tmp[j]=(tmp[j]+1ll*ans[i]*res[j])%mod;
                for(int i=0;i<m;i++) ans[i]=tmp[i];
                break;
            }
            case '>':{
                memset(tmp,0,sizeof tmp);
                for(int i=0;i<m;i++) for(int j=0;j<m;j++) if(a[i]>a[j]) tmp[i]=(tmp[i]+1ll*ans[i]*res[j])%mod;
                else tmp[j]=(tmp[j]+1ll*ans[i]*res[j])%mod;
                for(int i=0;i<m;i++) ans[i]=tmp[i];
                break;
            }
            case '?':{
                memset(tmp,0,sizeof tmp);
                for(int i=0;i<m;i++) for(int j=0;j<m;j++) tmp[i]=(tmp[i]+1ll*ans[i]*res[j])%mod,tmp[j]=(tmp[j]+1ll*ans[i]*res[j])%mod;
                for(int i=0;i<m;i++) ans[i]=tmp[i];
                break;
            }
        }
    }
    return ans;
}
inline void work(){
    for(int i=0;i<m;i++) for(int j=1;j<=n;j++) a[j][i]=star::a[i][j-1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=len;j++) for(int k=0;k<m;k++) but[j][k]=(isdigit(s[j]) and s[j]-'0'==k);
        int* res=solve(1,len,a[i]);
        for(int j=0;j<m;j++)
            ans=(ans+1ll*res[j]*a[i][j])%mod;
    }
    printf("%d\n",ans);
}

即把 \(n\) 组数分开来讨论，求每种数贡献的方案数，最后乘上值加起来。

那么问题就在于求每种数的方案数，这样的工作我们需要做 \(n\) 遍，非常不划算。

然后发现，对于大小关系相同的每组数，每种数贡献的方案数是相同的，改变的只是它们的值，我们没有必要每次都算一遍方案数。

发现，一个数在一组数中的相对大小关系的情况总数只有 \(2^m\) 种，即是否比该数大。

那么我们预处理出一个数的所有相对大小关系总数（这个部分是 \(O(2^m|E|)\) 的），然后对于 \(n\) 组数每个枚举 \(m\) 个数差分统计答案即可（差分得到该数的方案数。此部分是 \(O(nmlogm)\) 的）。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<utility>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=5e4+10,maxm=12,S=1050,mod=1e9+7;
	int n,m,a[maxn][maxm],D,f[S],pos,b[maxm],ans;
	char s[maxn];
	pair<int,int> solve(){
		int num=0;bool ok=true;char lst='>';
		pair<int,int> ans(1,0),now,tmp;
		while(lst!=')' and ++pos)
			if(isdigit(s[pos])) num=s[pos]^48;
			else if(s[pos]=='(') now=solve(),ok=false;
			else ok and (now=make_pair((D>>num)&1,(D>>num)&1^1),0),
				ok=true,tmp=make_pair(0,0),
				lst!='>' and (tmp.second=(tmp.second+1ll*ans.second*now.second)%mod,tmp.first=(tmp.first+1ll*(ans.first+ans.second)*(now.first+now.second)-1ll*ans.second*now.second%mod+mod)%mod),
				lst!='<' and (tmp.first=(tmp.first+1ll*ans.first*now.first)%mod,    tmp.second=(tmp.second+1ll*(ans.first+ans.second)*(now.first+now.second)-1ll*ans.first*now.first%mod+mod)%mod),
				ans=tmp,lst=s[pos],num=0;
		return ans;
	}
	inline bool cmp(const int &x,const int &y){return a[pos][x]<a[pos][y];}
	inline void work(){
		n=read(),m=read();
		for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[j][i]=read();
		scanf("%s",s+1);s[strlen(s+1)+1]=')';
		for(D=0;D<(1<<m);D++) pos=0,f[D]=solve().second;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++) b[j]=j;
			pos=i;sort(b,b+m,cmp);
			for(int j=0,d=0;j<m;d|=(1<<b[j++]))
				ans=(ans+1ll*(a[i][b[j]]-(j?a[i][b[j-1]]:0))*f[d])%mod;
		}
		printf("%d\n",ans);
	}
}
signed main(){
	star::work();
	return 0;
}